// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
	"math/rand"
)

type Point struct {
	X, Y float64
}

type Cluster struct {
	Center Point
	Points []Point
}

func KMeans(points []Point, k int) []Cluster {
	// 使用随机中心初始化集群
	clusters := make([]Cluster, k)
	for i := 0; i < k; i++ {
		clusters[i].Center = Point{rand.Float64(), rand.Float64()}
	}

	for {
		// 将每个点分配给最近的集群
		for i := range points {
			minDist := dist(points[i], clusters[0].Center)
			nearest := 0
			for j := 1; j < k; j++ {
				d := dist(points[i], clusters[j].Center)
				if d < minDist {
					minDist = d
					nearest = j
				}
			}
			clusters[nearest].Points = append(clusters[nearest].Points, points[i])
		}

		// 更新聚类中心
		changed := false
		for i := range clusters {
			if len(clusters[i].Points) > 0 {
				newCenter := center(clusters[i].Points)
				if dist(newCenter, clusters[i].Center) > 0.0001 {
					changed = true
					clusters[i].Center = newCenter
					clusters[i].Points = []Point{}
				}
			}
		}

		// 当聚类中心不再变化时停止
		if !changed {
			break
		}
	}

	return clusters
}

func dist(a, b Point) float64 {
	dx := a.X - b.X
	dy := a.Y - b.Y
	return dx*dx + dy*dy
}

func center(points []Point) Point {
	var sumX, sumY float64
	for _, p := range points {
		sumX += p.X
		sumY += p.Y
	}
	return Point{sumX / float64(len(points)), sumY / float64(len(points))}
}

func main() {
	// 生成一些随机点
	points := make([]Point, 6)
	for i := range points {
		points[i] = Point{rand.Float64(), rand.Float64()}
	}

	// 使用 K-Means 对点进行聚类
	clusters := KMeans(points, 3)

	// 打印集群
	for i, c := range clusters {
		fmt.Printf("Cluster %d:\n", i)
		for _, p := range c.Points {
			fmt.Printf("\t(%f, %f)\n", p.X, p.Y)
		}
	}
}

//$ go run interview10-16.go
//Cluster 0:
//        (0.096970, 0.300912)
//Cluster 1:
//        (0.604660, 0.940509)
//        (0.664560, 0.437714)
//        (0.424637, 0.686823)
//        (0.515213, 0.813640)
//Cluster 2:
//        (0.065637, 0.156519)
